public class MergeTwoSortedLists {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 当两个链表都为空, 返回 null(其实下面两个 if 就包含了这层if的意思, 该if语句是可以删掉的)
        if(list1 == null && list2 == null) {
            return null;
        }

        // 一个链表走到空, 返回另一个链表
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }

        // 较小者作为头节点然后返回
        if(list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        }else {
            list2.next = mergeTwoLists(list2.next, list1);
            return list2;
        }
    }
}
